package com.kaifamiao.demo.d0810;

import org.w3c.dom.Node;

/**
 * 双端链表
 */
public class DoubleLinked {

    private Node head;

    private Node last;

    private int length;


    public boolean add(String value){
        // 创建一个节点， 创建一个 Node 对象
        Node node = new Node(last, value);

        // 链表中有元素吗
        if (head == null){
            // 链表没有元素
            head = node;
        } else {
            // 把元素添加进去
            last.next = node;
        }
        // 把添加的元素作为链表的最后一个元素
        last = node;
        length ++;

        return true;
    }

    public String remove(int index){
        checkIndex(index);
        // 被删除的元素
        Node current = null;
        if (index == 0){
            // 被删除的元素
            current = head;

            head = head.next;
            head.prev = null;

            current.next = null;
        } else {
            // 找被删除元素
            current = head; // index = 0;
            for (int i = 1; i <= index; i ++){
                current = current.next;
            }
            // 被删除元素的上一个元素
            Node prev = current.prev;
            // 被删除元素的下一个元素
            Node next = current.next;
            // 上一个元素的 next 指向下一个元素, 下一个元素的 prev 指向上一个元素
            prev.next = next;
            next.prev = prev;

            current.prev = null;
            current.next = null;
        }
        length --;
        return current.value;
    }

    public String set(int index, String value){
        checkIndex(index);
        Node current = head; // index = 0;
        for (int i = 1; i <= index; i ++){
            current = current.next;
        }
        String old = current.value;
        current.value = value;
        return old;
    }

    public boolean add(int index, String value){
        checkIndex0(index);
        Node add = new Node(value);
        // TODO
        if (index == 0){

        } else if (index == length){

        } else {

        }
        length ++;
        return true;
    }

    private void checkIndex0(int index){
        if (index < 0 || index > length){
            throw new NodeListIndexOutOfBoundsException("索引异常， index 应该是 0 到 " + length + "。但是接收到的是 " + index );
        }
    }

    public String get(int index){
        checkIndex(index);
        Node current = null;
        if (index < length / 2) {
            current = head; // index = 0;
            for (int i = 1; i <= index; i ++){
                current = current.next;
            }
        } else {
            current = last; // index = length - 1;
            for (int i = 0; i < (length - index - 1); i ++){
                current = current.prev;
            }
        }
        return current.value;
    }

    private void checkIndex(int index){
        if (index < 0 || index >= length){
            throw new NodeListIndexOutOfBoundsException("索引异常， index 应该是 0 到 " + (length - 1) + "。但是接收到的是 " + index );
        }
    }

    public int size(){
        return length;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder("DoubleLinked { ");
        String str = "";
        if (head != null){
            Node current = head;
            while(current != null){
//                sb.append(current.value + ", ");
                sb.append(current + ", ");
                current = current.next;
            }
            str = sb.substring(0, sb.length() - 2);
        } else{
            str = sb.toString();
        }

        str += " }";
        return str;
    }





    private class Node{

        private Node prev;

        private String value;

        private Node next;

        public Node(){}

        public Node(String value) { this.value = value; }

        public Node(Node prev, String value) {
            this.prev = prev;
            this.value = value;
        }

        public Node(Node prev, String value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next ;
        }

        @Override
        public String toString(){
            return this.value;
        }
    }

    private class NodeListIndexOutOfBoundsException extends IndexOutOfBoundsException {
        public NodeListIndexOutOfBoundsException(String msg){
            super(msg);
        }
    }

}
